﻿//#pragma once

#ifndef __HASH_TABLE__
#define __HASH_TABLE__

#include <vector>
//#include <utility>   // for std::pair	如果不报错，说明间接已被包含，无需在意
//#include <algorithm> // for lower_bound

template <class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return static_cast<size_t>(key);	// C++的强制类型转换
	}
};

template <>
struct HashFunc<string>
{
	// 字符串转换成整型，可以直接把字符ASCII码相加
	// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
	// 这⾥我们使⽤ BKDR 哈希的思路，⽤上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131等效果会⽐较好
	size_t operator()(const string& s)
	{
		size_t hash = 0;

		for (const auto& e : s)
		{
			hash += e;
			hash *= 131;	// 溢出时自行回绕，关键是尽量不重复
		}

		return hash;
	}
};

// 【除法散列法（h(key) = key % M）】作为哈希函数，开放定址法中的【线性探测】处理插入数据时的冲突
namespace open_address
{
	// 强枚举类型，和类的使用方式类似，使用成员时指名类域即可
	enum class State
	{
		EXIST,
		EMPTY,
		DELETE,
	};

	template <class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = State::EMPTY;
	};

	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	private:
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			// Note: assumes long is at least 32 bits.
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
			  53,         97,         193,       389,       769,
			  1543,       3079,       6151,      12289,     24593,
			  49157,      98317,      196613,    393241,    786433,
			  1572869,    3145739,    6291469,   12582917,  25165843,
			  50331653,   100663319,  201326611, 402653189, 805306457,
			  1610612741, 3221225473, 4294967291
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);	// lower_bound用于获取[first, last)迭代器范围内大于或等于指定值的某元素的迭代器
			return pos == last ? *(last - 1) : *pos;
		}

	public:
		HashTable()
			: _table(__stl_next_prime(0))
			, _n(0)
		{}

		// 不支持重复值的插入
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			// / 负载因⼦ >= 0.7 扩容
			if (_n * 10 >= _table.size() * 7)	// _n / _table.size() >= 0.7，int / int 的结果没有小数，用数学进行等价变化
			{
				// 类似深拷⻉现代写法。新表中插⼊旧表数据后，交换指向新表数据空间和旧表数据空间的指针即可，简单高效
				HashTable<K, V, Hash> newht;
				newht._table.resize((__stl_next_prime(_table.size() + 1)));	// 注意必须+1才能正确扩容

				for (const auto& e : _table)
				{
					if (State::EXIST == e._state)
					{
						newht.Insert(e._kv);
					}
				}

				_table.swap(newht._table);
			}


			Hash hash;
			size_t hash0 = hash(kv.first) % _table.size();
			size_t hashi = hash0, i = 1;

			for (; State::EXIST == _table[hashi]._state; ++i)
			{
				hashi = (hash0 + i) % _table.size();	// 线性探测
			}

			_table[hashi]._kv = kv;
			_table[hashi]._state = State::EXIST;
			++_n;

			return true;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* res = Find(key);

			if (res)
			{
				res->_state = State::DELETE;
				--_n;

				return true;
			}

			return false;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hash;
			size_t hash0 = hash(key) % _table.size();

			for (size_t hashi = hash0, i = 1; State::EMPTY != _table[hashi]._state;)
			{
				//if (State::EXIST == _table[hashi]._state && _table[hashi]._kv.first == key)
				if (State::EXIST == _table[hashi]._state && key == _table[hashi]._kv.first)
				{
					return &_table[hashi];
				}

				// 线性探测
				hashi = (hash0 + i) % _table.size();
				++i;
			}

			return nullptr;
		}

	private:
		vector<HashData<K, V>> _table;
		size_t _n = 0;	// 表中存储的数据个数
	};
}

// 【除法散列法（h(key) = key % M）】作为哈希函数，开放定址法中的【线性探测】处理插入数据时的冲突
namespace hash_bucket
{
	template <class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode* _next;

		HashNode(const pair<K, V>& kv)
			: _kv(kv)
			, _next(nullptr)
		{}
	};

	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	private:
		typedef HashNode<K, V> Node;

		inline unsigned long __stl_next_prime(unsigned long n)
		{
			// Note: assumes long is at least 32 bits.
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
			  53,         97,         193,       389,       769,
			  1543,       3079,       6151,      12289,     24593,
			  49157,      98317,      196613,    393241,    786433,
			  1572869,    3145739,    6291469,   12582917,  25165843,
			  50331653,   100663319,  201326611, 402653189, 805306457,
			  1610612741, 3221225473, 4294967291
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);	// lower_bound用于获取[first, last)迭代器范围内大于或等于指定值的某元素的迭代器
			return pos == last ? *(last - 1) : *pos;
		}

	public:
		HashTable()
			: _table(11)	// C++中指针类型默认用nullptr初始化。测试时可将初始化大小为11 __stl_next_prime(0)
			, _n(0)
		{}

		// 拷贝构造和赋值重载也需要，暂未实现

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			Hash hash;
			size_t hash0 = 0;

			// 负载因子 == 1时扩容
			// 直接移动旧表的结点到新表，效率更好
			if (_n >= _table.size())
			{
				// 1、遍历旧表，为数据重新申请空间并插入新表中。不推荐
				/*HashTable newht;
				newht._table.resize(__stl_next_prime(_table.size() + 1), nullptr);

				for (const auto& e : _table)
				{
					for (Node* cur = e; cur;)
					{
						newht.Insert(cur->_kv);
						cur = cur->_next;
					}
				}
				
				_table.swap(newht._table);*/
				

				// 2、错误代码，未考虑新表扩容后，旧数据映射到新表的位置也会变化
				/*HashTable newht;
				newht._table.resize(__stl_next_prime(_table.size() + 1), nullptr);

				for (const auto& e : _table)
				{
					if (e)
					{
						hash0 = hash(e->_kv.first) % newht._table.size();
						newht._table[hash0] = e;
					}
				}
				
				_table.swap(newht._table);
				*/

				// 3、结合链表的结构特点，直接移动旧表中的节点即可
				vector<Node*> newTable(__stl_next_prime(_table.size() + 1), nullptr);

				for (size_t i = 0; i < _table.size(); ++i)
				{
					for (Node* cur = _table[i], *next = nullptr; cur; cur = next)
					{
						next = cur->_next;

						hash0 = hash(cur->_kv.first) % newTable.size();
						cur->_next = newTable[hash0];
						newTable[hash0] = cur;
					}

					_table[i] = nullptr;	// 不可缺少。后续交换指针后，newTable中记录的指针节点会被释放
				}

				_table.swap(newTable);	
			}

			Node* newnode = new Node(kv);
			hash0 = hash(kv.first) % _table.size();

			// 头插
			newnode->_next = _table[hash0];
			_table[hash0] = newnode;
			++_n;
			
			return true;
		}

		bool Erase(const K& key)
		{
			Hash hash;
			size_t hash0 = hash(key) % _table.size();

			// 某位置的哈希桶节点数量 == 1 和 > 1 分情况讨论即可
			// 方式1
			/*if (key == _table[hash0]->_kv.first)
			{
				_table[hash0] = nullptr;
				delete _table[hash0];
				--_n;

				return true;
			}
			else
			{
				for (Node* cur = _table[hash0], *prev = cur, *next = nullptr; cur;)
				{
					next = cur->next;
					if (key == cur->_kv.first)
					{
						prev->_next = next;
						delete cur;
						--_n;

						return true;
					}

					prev = cur;
					cur = next;
				}
			}*/
			// 方式2
			for (Node* cur = _table[hash0], *prev = nullptr, *next = nullptr; cur;)
			{
				next = cur->_next;

				if (key == cur->_kv.first)
				{
					if (nullptr == prev)
					{
						// 只有一个节点（头节点）
						_table[hash0] = nullptr;
					}
					else
					{
						// 2个及以上的节点
						prev->_next = next;
					}
					
					delete cur;
					--_n;

					return true;
				}

				prev = cur;
				cur = next;
			}
			
			return false;
		}

		Node* Find(const K& key)
		{
			size_t hash0 = Hash()(key) % _table.size();

			for (Node* cur = _table[hash0]; cur;)
			{
				if (key == cur->_kv.first)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

		~HashTable()
		{
			for (auto e : _table)
			{
				for (Node* cur = e, *next = nullptr; cur; cur = next)
				{
					next = cur->_next;
					delete cur;
				}

				e = nullptr;
			}

			_n = 0;
		}

	private:
		vector<Node*> _table;	// 指针数组
		size_t _n;				// 表中存储的数据个数

		// 1、使用自己实现的红黑树
		//struct Data
		//{
		//	ListNode* _head;
		//	RBTreeNode* _root;
		//	size_t _len;  // <= 8 存链表，>8 存红黑树 
		//};

		//vector<Data> _tables;
		//size_t _n = 0;		   // 表中存储数据个数

		// 2、使用现成的容器实现，较为简单
		//struct Data
		//{
		//	list<pair<K, V>> _list;
		//	map<K, V> _map;
		//	size_t _len;  // <= 8 存链表，>8 存红黑树 
		//};

		//vector<Data> _tables;
		//size_t _n = 0;		   // 表中存储数据个数
	};
}

#endif